Industry regularly employs information systems to solve complex combinatorial problems, e.g., computerized scheduling programs to manage the allocation of manufacturing equipment, manpower, and other resources amongst various projects. In computational complexity theory, combinatorial optimization problems are frequently classified as “NP-hard,” and in real world applications it is impossible to calculate a truly optimal solution to an NP-hard combinatorial problem using practical quantities of computational resources for practical periods of time. Mathematicians and computer scientists have developed various approaches for finding good solutions (as opposed to singularly optimal solutions) for combinatorial problems such as Resource Constrained Project Scheduling (“RCPS”) and the Traveling Salesman Problem (“TSP”), and such approaches may frequently be applied to more than one form of combinatorial problem. Software developers and vendors have naturally developed differing implementations of such known solution approaches for various types of industries, types of users, types of computer hardware, etc. Consequently, the marketplace for such information systems, or “combinatorial solvers,” includes a range of competing options which have varying features, capabilities, and/or underlying solution approaches, and prospective purchasers face a need to evaluate at least a subset of those competing options prior to making a purchase decision.
Only in rare instances can any solution approach be mathematically proven to reliably find a singularly optimal solution to a combinatorial problem, so that by and large prospective purchasers seeking to compare the performance of combinatorial solvers must benchmark candidate solvers against one or more trial scenarios. However, benchmarking combinatorial solvers presents some unique challenges. Because a combinatorial solver cannot practically assess the entire population of solutions for a particular problem (a “problem solution space”), combinatorial solvers cannot properly be compared based upon whether the solver finds the optimal solution for a benchmark problem (if it is even known), nor based upon the raw computational effort required to find a good solution meeting some measurable criterion of quality, such as a cycle time for an RCPS scenario or a distance to be traveled for a TSP scenario. Instead, each combinatorial solver will tend to develop solutions that are influenced by a combination of the trial scenario and the solver's implementation of a solution approach (a “solver solution space”), and, unless the solution approach is entirely deterministic or exhaustive, a significant element of chance. Thus, in a benchmark trial, a strong solution approach with an inefficient implementation may only find average quality solutions, while a weak solution approach with a highly optimized implementation may find a superior quality solution. Yet, during longer operational uses, or when applied to more complex combinatorial scenarios, or if simply run in different testing circumstances (different trial scenario, different computing hardware, or merely a different number of permissible trials) the strong solution approach may prove to more reliably find better solutions. Although benchmark trials should seek to replicate a prospective purchaser's operating environment, time and resource constraints typically prevent all but the largest prospective purchasers from testing competing combinatorial solvers against representative real world scenarios on fully-scaled-up computer systems. Moreover, while academic research has gone to great lengths to develop benchmark methods which reduce the confounding effects of scenario-dependence, resource availability, and chance, no reliable method has been found to eliminate such effects. Consequently, current benchmarking methods tend to produce ambiguous, misleading, or unreliable results that, in general, are poor predictors of the performance of a combinatorial solver during otherwise routine applications of the solver in real world operations.
Finally, some existing benchmark methods can be influenced by ‘off-line engineering,’ in which the combinatorial solver's implementation of a solution approach is subtly influenced by, for instance, varying the order of the input conditions or fixing the value of a randomization seed in order to direct the combinatorial solver toward a previously determined solution for the benchmark problem. By applying a combinatorial solver to a known benchmark problem prior to a benchmark trial, varying the starting conditions, and then replicating the starting conditions under which the solver rapidly finds a particularly good solution to the problem, a solver can be subtly directed to ‘find’ the same good solution without altering the executable code of the solver. Because each combinatorial solver tends to have unique input and/or data storage formats, it may be possible to manipulate the ordering of the input conditions in order to influence the progress of the combinatorial solver through a problem solution space in ways which are not readily detectable as overt manipulation. Similarly, if a combinatorial solver uses a randomization seed (e.g., the content of a memory address) and pseudo-random number generator, it may be possible to manipulate the state of the computer to create a particular seed value and, in so doing influence the progress of the combinatorial solver. A combinatorial solver could thereby benefit from extensive pre-benchmark testing of the solver and solution space despite appearing to comply with the more limited constraints of the benchmark trial. Vendors may resist participating in benchmark trials because they suspect that other competitors will engage in such off-line engineering in order to influence the outcome of a benchmark comparison. Moreover, even if such concerns are addressed, vendors may challenge the results of competitive benchmarks, or even forbid the publication of benchmark results, out of fear of an unfavorable result attributable (realistically or not) to chance. Essentially any vendor can honestly say that they could have found a solution equal to or better than that found by another vendor if given a bit more time or a few more trials. However, using current benchmarking methods, there is no way to predict how much more time or how many more trials would likely be required.
Thus there is a need for a method of benchmarking a combinatorial problem, i.e., providing an approximate description of the population of potential solutions for a given combinatorial problem, as well for as an improved method of benchmarking the performance of a combinatorial solver given limited computational resources and limited amounts of time. Such methods may be used to describe the performance of a combinatorial solver relative to chance. Such methods may also be used in place of benchmark approaches which rank the output of combinatorial solvers for a single trial scenario, or even a suite of trial scenarios, to enhance the representativeness of the benchmark result with respect to different, non-benchmarked combinatorial problems of similar complexity. As will be discussed below, the results of the method may be employed to estimate the computational effort to be invested in order to obtain good solutions exceeding a measurable criterion of quality, allowing for more detailed evaluations of computational solvers which tend to develop solutions of similar quality.